513. Find Bottom Left Tree Value.go

package leetcode

import (
"github.com/halfrost/LeetCode-Go/structures"
)

// TreeNode define
typeTreeNode= structures.TreeNode

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 * Val int
 * Left *TreeNode
 * Right *TreeNode
 * }
 */

// 解法一 DFS
funcfindBottomLeftValue(root*TreeNode) int {
ifroot==nil {
return0
 }
res, maxHeight:=0, -1
findBottomLeftValueDFS(root, 0, &res, &maxHeight)
returnres
}

funcfindBottomLeftValueDFS(root*TreeNode, curHeightint, res, maxHeight*int) {
ifcurHeight>*maxHeight&&root.Left==nil&&root.Right==nil {
*maxHeight=curHeight
*res=root.Val
 }
ifroot.Left!=nil {
findBottomLeftValueDFS(root.Left, curHeight+1, res, maxHeight)
 }
ifroot.Right!=nil {
findBottomLeftValueDFS(root.Right, curHeight+1, res, maxHeight)
 }
}

// 解法二 BFS
funcfindBottomLeftValue1(root*TreeNode) int {
queue:= []*TreeNode{root}
forlen(queue) >0 {
next:= []*TreeNode{}
for_, node:=rangequeue {
ifnode.Left!=nil {
next=append(next, node.Left)
 }
ifnode.Right!=nil {
next=append(next, node.Right)
 }
 }
iflen(next) ==0 {
returnqueue[0].Val
 }
queue=next
 }
return0
}